/**
 * 对于 LIS ，我们还有一种更加快速的算法，即贪心 + 二分
 * low[i] 用来存储最长升序子序列长度为 i 时的最小元素
 * 这里注意：
 * 1.
 * 对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长
 * 2. low[] 数组中存储的元素并不一定是最长升序子序列
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
  int lengthOfLIS(vector<int> &nums) {
    if (nums.empty())
      return 0;
    int *low = new int[nums.size() + 1];
    // len 用来 low 数组的长度
    int len = 1;
    low[1] = nums[0];
    for (auto num : nums) {
      if (num > low[len])
        low[++len] = num;
      else {
        auto index = lower_bound(low, low + len, num);
        low[index - low] = num;
      }
    }
    return len;
  }
};
int main() { return 0; }